package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC67 {

    public String addBinary(String a, String b) {
        //ensure a > b
        if (a.length() < b.length()) {
            String tmp = b;
            b = a;
            a = tmp;
        }

        StringBuilder c = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1;
        int step = 0;
        for (; j >= 0; --j, --i) {
            int curSum = a.charAt(i) - '0' + b.charAt(j) - '0' + step;
            step = curSum / 2;
            curSum %= 2;
            c.insert(0, curSum > 0 ? '1' : '0');
        }
        for (; i >= 0; --i) {
            int curSum = a.charAt(i) - '0' + step;
            step = curSum / 2;
            curSum %= 2;
            c.insert(0, curSum > 0 ? '1' : '0');
        }
        if (step > 0) {
            c.insert(0, '1');
        }

        return c.toString();
    }

    public static void main(String[] args) {
        LC67 an = new LC67();
        System.out.println(an.addBinary("11", "1"));
    }
}
